package com.note.feng.leetcode.algorithms.easy.ten;

import java.util.Stack;

public class ThousandTwentyOne {
    /**
     * 1021 删除最外层的括号
     * 有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
     *
     * 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
     * 如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
     *
     * 给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
     *
     * 对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
     *
     * 示例 1：
     *
     * 输入：s = "(()())(())"
     * 输出："()()()"
     * 解释：
     * 输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
     * 删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
     * 示例 2：
     *
     * 输入：s = "(()())(())(()(()))"
     * 输出："()()()()(())"
     * 解释：
     * 输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
     * 删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
     * 示例 3：
     *
     * 输入：s = "()()"
     * 输出：""
     * 解释：
     * 输入字符串为 "()()"，原语化分解得到 "()" + "()"，
     * 删除每个部分中的最外层括号后得到 "" + "" = ""。
     *  
     * 提示：
     *
     * 1 <= s.length <= 105
     * s[i] 为 '(' 或 ')'
     * s 是一个有效括号字符串
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/remove-outermost-parentheses
     */
    /**
     * 解法：栈
     * 利用栈的特性，遇到 '(' 入栈，遇到 ')' 出栈，若栈为空，则得到一个原语，去掉两端的括号，就是当前原语的最终字符串
     * @param s
     * @return
     */
    public String removeOuterParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        StringBuffer res = new StringBuffer();
        StringBuffer pre = new StringBuffer();
        pre.append(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(')' == ch){
                stack.pop();
            }else {
                stack.push(ch);
            }
            pre.append(ch);
            if(stack.isEmpty() && !pre.toString().isEmpty()){
                int len = pre.length();
                res.append(pre.substring(1, len - 1));
                pre.delete(0, len);
            }
        }
        return res.toString();
    }

    /**
     * 解法：栈
     * 是对上面方法的优化，效率更高
     * @param s
     * @return
     */
    public String removeOuterParentheses2(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(')' == ch){
                stack.pop();
            }
            if(!stack.isEmpty()){
                res.append(ch);
            }
            if('(' == ch){
                stack.push(ch);
            }
        }
        return res.toString();
    }
}
